package set_map.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yuisama
 * @date 2022/01/12 20:02
 **/
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Num138 {
    public Node copyRandomList(Node head) {
        // 1.边界条件
        if (head == null) {
            return null;
        }
        // 2.建立链表节点的映射关系
        // 旧1 = 新1
        Map<Node,Node> nodeMap = new HashMap<>();
        // 3.遍历原链表，新建链表节点，建立起映射关系
        for (Node x = head;x != null;x = x.next) {
            Node newNode = new Node(x.val);
            nodeMap.put(x,newNode);
        }
        // 4.通过映射关系来连接新链表的next引用和random引用
        for (Node x = head;x != null;x = x.next) {
            nodeMap.get(x).next = nodeMap.get(x.next);
            nodeMap.get(x).random = nodeMap.get(x.random);
//            // 旧1.next = 旧2
//            // 新1.next = 新2
//            // nodeMap中 旧1 = 新1
//            // 新1
//            Node newX = nodeMap.get(x);
//            // 旧2 = 新2
//            Node newXNext = nodeMap.get(x.next);
//            // 新1.random 与旧1.random相同映射
//            Node newXRandom = nodeMap.get(x.random);
//            newX.next = newXNext;
//            newX.random = newXRandom;
        }
        // 新链表头节点 = nodeMap.get(head);
        // 旧head = 新head
        return nodeMap.get(head);
    }
}